#pragma once

class EmptyException {};

template <typename T>
struct StackNode {
	T data;
	StackNode* next;

	StackNode() :next(nullptr) 
	{}
	StackNode(T data, StackNode* next):data(data),next(next)
	{}
};

template <typename T>
struct Stack {
	StackNode<T>* head;

	Stack();
	bool isEmpty();
	T top();
	void push(T data);
	T pop();
};

template <typename T>
Stack<T>::Stack() {
	head = new StackNode<T>;
}

template <typename T>
bool Stack<T>::isEmpty() {
	if (!head->next) return true;
	else return false;
}

template <typename T>
T Stack<T>::top() {
	if (isEmpty()) throw new EmptyException;
	else return head->next->data;
}

template <typename T>
void Stack<T>::push(T data) {
	head->next = new StackNode<T>(data, head->next);
}

template <typename T>
T Stack<T>::pop() {
	T returnData;
	StackNode<T>* p = head->next;
	head->next = p->next;
	returnData = p->data;
	delete p;

	return returnData;
}